package m202406.d23;

import java.util.*;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/24 11:33
 */
public class Q543 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        Q543 q543 = new Q543();
        q543.diameterOfBinaryTree(root);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<TreeNode> all = new Stack<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            all.push(poll);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        Map<TreeNode, NodeExtend> map = new HashMap<>();
        while (!all.isEmpty()) {
            TreeNode pop = all.pop();
            if (isLeaf(pop)) {
                map.put(pop, new NodeExtend());
                continue;
            }
            NodeExtend left = map.get(pop.left);
            NodeExtend right = map.get(pop.right);
            map.put(pop, new NodeExtend(left, right));
        }

        int max = 0;
        for (NodeExtend value : map.values()) {
            max = Math.max(max, value.max);
        }
        return Math.max(max - 1, 0);
    }

    private boolean isLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }

    private static class NodeExtend {
        private int l;
        private int r;
        private int max;

        public NodeExtend() {
            this.l = 0;
            this.r = 0;
            this.max = 0;
        }

        public NodeExtend(NodeExtend left, NodeExtend right) {
            if (left != null) {
                this.l = Math.max(left.l, left.r) + 1;
            }
            if (right != null) {
                this.r = Math.max(right.l, right.r) + 1;
            }
            this.max = this.l + this.r + 1;
        }
    }


    int max = 0;

    public int diameterOfBinaryTree1(TreeNode root) {
        maxDepth(root);
        return Math.max(max - 1, 0);
    }


    private int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = maxDepth(node.left);
        int r = maxDepth(node.right);
        max = Math.max(max, l + r + 1);
        return Math.max(l, r) + 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
